let oriArray = Array.from({ length: 10 }, () => {
  return Math.floor(Math.random() * 200);
});
console.log('oriArray: ', oriArray);

function bobbleSort(array) {
  for (let i = 0; i < array.length - 1; i++) {
    for (let j = 0; j < array.length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
      }
    }
  }
  return array;
}

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {
      if (array[j] < array[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      [array[i], array[minIndex]] = [array[minIndex], array[i]];
    }
  }
  return array;
}

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    let curItem = array[i];
    let j = i - 1;
    while (j >= 0 && curItem < array[j]) {
      array[j + 1] = array[j];
      j--;
    }
    array[j + 1] = curItem;
  }
  return array;
}

function mergeSort(array) {
  let len = array.length;
  if (len <= 1) {
    return array;
  }
  let mid = len >> 1;
  let leftArr = array.slice(0, mid);
  let rightArr = array.slice(mid);

  let newLeftArr = mergeSort(leftArr);
  let newRightArr = mergeSort(rightArr);

  let i = 0;
  let j = 0;
  let newArr = [];
  while (i < newLeftArr.length && j < newRightArr.length) {
    if (newLeftArr[i] < newRightArr[j]) {
      newArr.push(newLeftArr[i]);
      i++;
    } else {
      newArr.push(newRightArr[j]);
      j++;
    }
  }
  if (i < newLeftArr.length) {
    newArr.push(...newLeftArr.slice(i));
  }
  if (j < newRightArr.length) {
    newArr.push(...newRightArr.slice(j));
  }
  return newArr;
}

function quickSort(array) {
  function fun(left, right) {
    if (left > right) return;
    let P = array[right];
    let l = left;
    let r = right - 1;
    while (l <= r) {
      while (array[l] < P) l++;
      while (array[r] > P) r--;
      if (l <= r) {
        [array[l], array[r]] = [array[r], array[l]];
        l++;
        r--;
      }
    }
    [array[l], array[right]] = [array[right], array[l]];
    fun(left, r);
    fun(l + 1, right);
  }
  fun(0, array.length - 1);
  return array;
}

function quickSort1(array) {
  if (array.length <= 1) return array;
  let P = array[array.length - 1];
  let leftArr = [];
  let rightArr = [];
  for (let i = 0; i < array.length - 1; i++) {
    const element = array[i];
    if (element > P) {
      rightArr.push(element);
    } else {
      leftArr.push(element);
    }
  }
  return quickSort1(leftArr).concat(P, quickSort1(rightArr));
}

console.log('quickSort: ', quickSort1(oriArray));
